// @algorithm @lc id=295 lang=cpp 
// @title find-median-from-data-stream

class MedianFinder {
	priority_queue<int> left; // 大顶堆
	priority_queue<int,vector<int>,greater<int>> right; // 小顶堆
public:
    /** initialize your data structure here. */
    MedianFinder() {
    }
    
    void addNum(int num) {
		if(left.empty()){
			left.push(num);
			return;
		}
		if(left.size() > right.size()){
			if(left.top() <= num){
				right.push(num);
				return;
			}
			right.push(left.top());
			left.pop();
			left.push(num);
			return;
		}
		if(num <= right.top()){
			left.push(num);
			return;
		}
		left.push(right.top());
		right.pop();
		right.push(num);
    }
    
    double findMedian() {
		if(left.empty()) return 0;
		if(left.size() > right.size()) return left.top();
		return (left.top()+right.top())/2.0;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */